Nhà thờ Phú Nhai nguyên thủy được tạo dựng bằng gỗ, lợp bồi do linh mục Chính xứ Emmanuel Rianô Hòa cho xây dựng vào năm 1866, ngay sau khi vua Tự Đức ký sắc lệnh tha đạo, chấm dứt gần 3 thế kỷ Kitô giáo bị bách đạo tại Việt Nam.

Năm 1881, Giám mục Hòa cùng với linh mục Barquerô Ninh xây nhà thờ thứ hai theo kiến trúc Á Đông và hai tháp chuông.

Năm 1916, Giám mục Phêrô Munagôri Trung và linh mục Morênô xây nhà thờ thứ ba theo Kiến trúc Gothic. Khánh thành năm 1922 nhưng bị cơn bão lớn tàn phá nặng nề vào ngày 24 tháng 6 năm 1929.

Năm 1930, để có kinh phí xây dựng nhà thờ, bề trên giáo phận đã mở cuộc xổ số trên toàn quốc. Sau nhiều biến cố lịch sử, nhà thờ này được xây dựng lại, hoàn thành và xức dầu cung hiến thánh đường vào ngày lễ Đức Mẹ Vô Nhiễm Nguyên Tội 8 tháng 12 năm 1933.

Tháng 11/1949, một bộ phận quân viễn chinh Pháp chiếm đóng Phú Nhai, lấy nhà thờ có ngọn tháp cao làm điểm uy hiếp các vùng, lấy hai dãy hành lang làm trụ sở làm việc và dãy hướng Nam là nơi giam giữ, tra tấn cán bộ cách mạng, nhanh chóng xây dựng công sự đào hầm hào, đắp đường Ức từ Phú Nhai ra Bùi Chu để tiện việc hành quân, linh mục Lương Huy Hân làm tổng tuyên úy[1]

Sau thời gian chiến tranh bị hư hại, Nhà thờ được trùng tu tôn tạo bởi Giám mục Đa Minh Nguyễn Chu Trinh khởi công từ ngày 17 tháng 3 năm 2003 cho đến 26 tháng 9 năm 2004 thì hoàn thành như diện mạo hiện nay.